Network layer

Intro

任务：packets 从开始到目的地传送

如何选择一个path：
1.Routing Protocol，Router
2.Routed Protocol： IPV4，IPV6
3.Others

Def of路由：路由是指路由器从一个接口上收到数据包，根据数据包的目的地址进行定向并转发到另一个接口的过程

About newwork layer

在TCP/IP 是Internet 在OSI是Newwork

Function：transport packet from source to destination all the way

Service types provided by network layer：
1.Connection oriented service：X.25, ATM
2.Connectionless service：IP

Structure of communication subnet：（各对应一种连接和无连接）
o.Virtual-circuit subnet
　１.Select a path when connection is established
　２.Each packet has a connection-number
　３.Connection is removed when communication is over

o.Datagram subnet
１.Each datagram has destination-address
３.Each datagram look for path independently

Datagram subnet

传输步骤：
1.消息的长度是最大数据包长度的4倍，所以，网络层必须将消息拆分成4个数据包： 1 2 3 4
2.用某种点到点协议（比如 PPP ）将这些数据包依次发送给路由器 A.
3.ISP 将消息的传输任务接管过来。每一台路由器都有一个内部表，它指明了针对每一个可能的目标地址应该将数据包送到哪里去。（这个表由两部分组成：目标地址和通往目标地址所使用的出境线路。当然，只能使用直接连接的线路）（中间可能动态调整路线，因为拥堵等）

Virtual-circuit subnet

虚电路背后的思想是避免为每个要发送的数据包选择一条新路径，当建立一个连接时，从源机器到目标机器之间的一条路径就被当作这个连接的一部分确定了下来，并且保存在这些中间路由器的表中

如果两个source：
尽管第一个路由很容易区分出标识连接1的数据包是来自 Hl 还是来自 H3 ，但是，之后的路由无法区分它们。基于这个原因， 第一个路由给第二个连接的出境流量分配一个不同的连接标识符。这种避免冲突的做法说明了为什么路由器需要具备替换出境数据包中连接标识符的能力。

比较

都需要路由算法

如何建立routing table

Static routing：
　Configured by administrator: ip route

Dynamic routing
　Routing algorithm
　Distance vector routing（D-V）
　Link state routing（L-S）

Static routing

DEf：由管理员配置的路由表项称为静态路由

特点：
1.Fit for small, stable network，cost less
2.Default routing：both of destination network address and subnet mask is 0.0.0.0，（网络地址，网络掩码默认为0）
3.Can use Windows route print, check routing table

Dynamic routing

Def：路由协议获取的路由表项称为动态路由

特点：Fit for big, variational network，cost more

Routing protocol classification

一个被动一个主动
１.Routed protocol
　　example：IP、IPX
２.Routing protocol
　　Distance vector routing
　　Link state routing
　　Hybrid routing

Routing Algorithm

Def： 路由算法 routing algorithm ）是网络层软件的一部分，它负责确定一个入境数据包应该被发送到哪一条输出线路上

使用情况：如果网络内部使用了数据报，那么路由器必须针对每一个到达的数据包重新选择路径，因为自上一次选择了路径之后，最佳路径可能已经发生了改变。如果网络内部使用虚电路，那么只有当建立一条新的虚电路时，才需要做路由决策：
此后，数据包只要沿着己经建立的路径向前传递即可

设计问题：Correctness, simplicity, robustness, stability, fairness, and optimality (contradictory、trade-off)

Classfication：
　　Static algorithm（not self-adaptive）
　　Dynamic algorithm（ self-adaptive ）

Metric in routing algorithm（度量）

量度，代价，开销，成本
Common metric：
1.Path length：hop (跳数)
2.reliability：error rate on line
3.Delay
4.bandwidth
5.Load of router
6.Communication cost

Static routing algorithm

Optimization principle（最优化原理）

原理：如果路由器J在路由器I到K的最优路径上，那么从J到K的最优路径也在同一条路径上

Sink树：从所有源到给定目的地的最优路由集合形成以目的地为根的树(称为sink树)
特点：
1.不一定是唯一的
2.所有路由算法的目标都是发现和使用所有路由器的汇聚树

Dijkstra 算法

Dijkstra algorithm（1959）：compute shortest path using weight on communication-line

Pay attention：
1.path with lest line may not be shortest path
2.The shortest path may be the fastest one
实现可以用dijkstram

Flooding algorithm（泛洪算法）

Flooding：Every incoming packet is sent out on every outgoing line except the one it arrived on（(不计算路径，有路就走)）
问题：duplicate packets
解决：
在packet-head中增加计数器，通过节点时减少1;当counter为0时，丢弃报文
每个节点设置一个注册表，报文被丢弃的时候它再次到达一个节点
Flooding selectively
缺点：重复的数据包多于两个，浪费带宽
优点:可靠性高，路径短，在军事中使用频繁

Dynamic algorithm

如何实现动态的性质：
1.如果路由器需要通信，它们必须使用相同的语言，即相同的路由协议
2.新路由器必须主动介绍自己(打招呼)
3.定期发送hello包以了解对方的健康状况(保持存活)

Def：。虽然动态路由算法比上述泛洪算法更复杂，但由于这些算法能找到当前网络拓扑中的最短路径，因而更加有效。特别地，两个动态算法最为流行，即距离矢量路由算法和链路状态路由算法

Distance Vector Routing（距离矢量路由选择）

Def：通过让每个路由器维护一个表(即矢量)来操作，给出每个目的地的最佳已知距离以及到达目的地的线路。

特点：D-V算法是动态的、分布式的。它常用于小型网络中，RIP是DV的典型例子（Routing information protocol）

Working principle of DV：

规则：
1.Each router use two vectors, Di and Si ,to denote the distance from a node to all other nodes and next node (hop)
2.Exchange path-information among Neighbor routers
3.每个节点根据路径信息更新自己的路由表

数学描述：

Update routing table

After exchange vector:
　　Update distance : dij= Min[dix+ dxj] ( x ∈A )
　　　　A—collection of neighbors of node I;
　　　 dij—the shortest distance from i to j;
　　　dix—the shortest distance from i to x;
　　　 dxj—the shortest distance from x to j
　　Update next node: Sij= x

为什么AJdelay是8，但表里是9：这不是错误，可能就是很正常，因为不同的delay不同，每一次测试都不同

Characteristic of D-V algorithm

优点：算法简单
缺点：交换的信息太大 ；路径信息传播缓慢，路径信息可能不同；收敛速度慢，导致无限计数问题 ；不适合大型网络

RIP

Def：RIP is a D-V routing protocol
RIP uses hop (跳数) as metric
限制：When metric is bigger than 15, the destination is deemed to unreachable
Default sending period is 30 seconds

缺点：
当目标网络的指标大于 15（太小）时无法到达RIP的指标是跳数，也就是路由器的编号，
它没那么合理在实践中，
通常数到无穷大，然后缓慢收敛

The problems induced by DV

Representation
1.routing loop（路由环路）
2.Count to infinite（计数到无穷问题）
3.slow Convergence （收敛慢的问题）

Cause：Trust wrong routing information

问题：好消息跑得快，坏消息传的慢
但实际它有一个严重的缺陷：虽然它总是能够收敛到正确的答案，但速度可能非常慢。尤其是，它
对于好消息的反应非常迅速，而对于坏消息的反应异常迟缓

Link State routing（链路状态路由）

The idea behind link state routing consists of five parts:
　 1.Discover its neighbors and learn their network addresses.(发现它的邻居节点，并了解其网络地址。)
　2.Measure the delay or cost to each of its neighbors.(设置到每个邻居节点的距离或者成本度量值。)
　3.Construct a packet telling all it has just learned.(构造一个包含所有刚刚获知的链路信息包。)
　4.Send this packet to all other routers.
　5.Compute the shortest path to every other router.

Learning about the Neighbors

当路由器启动时，它会在每个点对点线路上发送一个特殊的 HELLO 数据包。
另一端的路由器应该发回一个回复，告诉它是谁（使用全局唯一的名称）
当两个或多个路由器通过 LAN 连接时，可以将 LAN 建模为节点。

Measuring Line Cost

为了寻找最短路径，链路状态路由算法需要每条链路以距离或成本度量：

为了确定线路的成本，路由器会发送一个特殊的 — ECHO 数据包，并且另一端需要立即发回。
通过测量往返时间，发送路由器可以合理估计延迟。为了获得更好的结果，可以进行多次测试，并使用平均值。

要考虑负载，必须在 ECHO 数据包排队时启动往返计时器。
要忽略负载，应在 ECHO 数据包到达队列前面时启动计时器。

如果网络在地理上分散，链路的延迟可以作为成本的组成部分，这样才能更好地选择较短链路上的路径。

构造链路状态包

一旦收集到了所需要的交换信息，每个路由器的下一步工作是构建一个包含所有这些信息的数据包。该数据包的内容首先是发送方的标识符，接着是一个序号（ Seq ）和年龄，以及一个邻居列表。对于每个邻居，同时要给出到这个邻居的延迟。
包含：ID of the sender，sequence number，age，list of neighbors，delay to each neighbor

构造链路状态数据包很容易。难的是确定什么时候构造数据包。一种可能的做法是周期性地创建数据包，也就是说，以一定的时间间隔创建链路状态数据包。另一种可能做法是每当发生某些重要的事情时才创建数据包，比如当一条线路断掉或者一个邻居节点停机时，或当它们重新恢复运行时，或当它们的特性发生了一定变化时。

分发链路状态包

最基本的算法：
1.每个状态数据包都包含一个序列号,该序列号会随着发送的每个新数据包而增加。
2.路由器跟踪它们看到的所有（源路由器、序列）对。
3.当一个新的链路状态数据包进来时,它会与已经看到的数据包列表进行检查。
　如果它是新的，则在所有线路上转发，除了它到达的那条线路（即洪水）。
　如果它是重复的,它被丢弃。
　如果序列号低于迄今为止看到的最高序列号的数据包到达，则会因已过时而被拒绝。

Problem：
1.序列号可能会环绕，造成混淆。（解决：Solution: using a 32-bit sequence number. With one packet per second, it would take 137 years to wrap around.）
2.If a router ever crashes, it will lose track of its own sequence number. If it starts again at the sequence number 0, new packets will be rejected as obsolete/duplicate by other routers.（如果一个路由器崩溃了，那么它将丢失所有的序号记录表。如果它再从 开始，那么，下一个数据包将被作为重复数据包而拒绝。）
3. If a sequence number is ever corrupted and 65,540 is received instead of 4 (a 1-bit error), packets 5 – 65540 will be rejected as obsolete.（如果一个序号被破坏了，比如发送方发送的序号为4，但是由于产生了1位错误，所以接收方看到的序号是 65 540 ，那么，序号从 5到65 540 的数据包都将被当作过时数据包而拒绝接受，因为接收方认为当前的序号是 65 540）

solution：所有这些问题的解决方案都一样 在每个数据包的序号之后包含一个年龄（ age ）宇段，并且每秒钟将年龄减1 。当年龄字段的值被减到 0时，来自路由器的该信息将被丢弃

通常情况下，每隔一段时间，比如说 10 秒，一个新的数据包就会到来：所以，只有当一个路由器停机时（或者 6个连续的数据包被丢失，这种情形发生的可能性不大），路由器信息才会超时。在初始泛洪过程中，每个路由器也要递减 age 宇段，这样可以确保没有数据包丢失，也不会无限制生存下去（如果一个数据包的 age为0 ，则被丢弃〉。

对基本算法的一些改进使其更加robust(强健)：
当一个链路状态数据包被泛洪到一个路由器时，它并没有立即被排入队列等待传输。相反，它首先被放到一个保留区中等待一段时间。如果在这个数据包被转发出去之前，另一个来自于同一个源路由器的链路状态数据包也到来了，那么就比较它们的序号。如果两个数据包的序号相等，则丢弃重复数据包。如果两者不相等，则丢弃老的数据包。为了防止线路产生错误导致丢包和错包，所有的链路状态数据包都要被确认。

计算新路由

1.一组完整的链路状态数据包允许路由器构建整个子网的图
(一旦路由器己经积累了全部的链路状态数据包之后，它就可以构造出完整的网络图，因为每条链路都己经被表示出来了。事实上，每条链路被表示了两次，每个方向各表示一次。不同方向的链路可能有不同的成本。最短路径计算可找到从 与从 不同
的路径）

2.我们现在可以使用Dijkstra的算法来计算路由器之间的最短路径。

3.我们可以在路由器中安装此信息以“引导数据包”（设置路由表）

优缺点分析

Advantages
　　Consistency of every router is good
　　Convergence is good
　　Fit for big network
Disadvantages
　　Each router requires bigger storage-space
　　Computing workload is great

Example of L-S routing protocol

1.Open shortest path first
2.Use graph to replace real network
　　Every router is a node
　　Measure cost（metric）
　　May have a few graphs
3.Computing shortest path

OSPF

DEf：ospf全称（Open Shortest Path First，OSPF）开放式最短路径优先，是被最广泛使用的一种动态路由协议，是一种链路状态协议。具有路由变化收敛速度快、无路由环路、支持变长子网掩码（VLSM）和汇总、层次区域划分等优点。

其他概念：
DR：一个广播性、多接入网络中的指定路由器（Designated Router）
BDR：为减小多路访问网络中OSPF流量，OSPF会选择一个指定路由器（DR）和一个备份指定路由器（BDR）。当多路访问网络发生变化时，DR负责更新其他所有OSPF路由器。BDR会监控DR 的状态，并在当前DR发生故障时接替其角色
DR BDR存在于多路访问网络中，作用是减少区域内的同步次数，降低路由器的内存消耗，减少了路由流量更新，确保同一区域内的路由器拥有相同的LSDB
LSDB：每台设备都有个表格，LSDB，链路状态数据库，LSDB中每一条就是LSA，链路状态公告

特点：
OSPF是一种基于开放标准的路由协议，是igp中最常用、最优的协议（自主系统），工作也IP层智商
1.能被大型网络使用
2.No routing-loop
3.支持VLSM使
4.用带宽作为度量(10^8/BW)
5.收敛速度快
6.分区域且同区域LSDB相同（不同区域连接用边路ABR联系）

Single-area OSPF
OSPF通过将路由器划分为不同的区域,并控制各区域之间的链路状态交换,来减少链路状态广播量,提高OSPF的扩展性
1.通常情况，大的OSPF网络会分为subarea，区域0是骨干区域。（多种区域）
2.RouterID：一个无标志32字节的整数。是一个路由的唯一标识符，并且呗包括在AS中
3.Protocol number：89，在IP packet的头部
4.TTL=1：一般情况下，OSPF报文不能传输，但虚连接是例外

信息类型：
Hello：用来发现邻居是谁（确定发送hello包，确定邻居是谁）
Link State update（LSU）：向其邻居提供发送方的开销
Link state ack（LSA）：确认LSU
Database description（DD）：宣布发送方有哪些更新
Link State request（LSR）：从伙伴请求信息

具体步骤:
1.Construct Full-adjacency realationship（建立拓扑关系，建立邻接关系，但不是所有都建立邻接关系）
2.Select DR and BDR（只与DR和BDR确立关系）（选择一个组长DR，然后他收集信息，再下发给组员，防止组长挂掉，会选个副组长BDR，组长和副组长都和组员连接）
3.discover routing
4. 选择最佳路由
5. 维护路由信息（有变化立刻更新，没变化30分钟一次）（更新:A先发LSA的摘要，B然后发送请求获得信息）

为什么选择路由：在一个共享的广播网络多台路由器建立OSPF，有可能会产生大量的OSPF邻居在这些大量的OSPF邻居发送大量的OSPF报文，造成其他路器接收到大量的OSPF重复报文浪费带宽资源和设备CPU计算资源 连接：

大型网络中的OSPF问题：
1.LSDB非常庞大，需要大量的存储空间。
2.计算最小生成树需要更多的时间，CPU的负载很重。（甚至可能重新计算）
3.网络拓扑结构变化频繁，网络结构多变often in turbulence（震荡）.（因为接口up或down路由器添加或删除就像一个湖）

建立路由邻接表

BGP

Def：BGP是一种增强的路径矢量路由协议，同时BGP是拥有丰富的策略控制技术的外部网关协议。多运行于AS与AS之间
BGP 其着眼点不在于自动发现网络拓扑，而在于在AS之间选择最佳路由和控制路由的传播。

AS是什么：（AS (autonomous system)自治系统（BGP一个路由器只能处于一个AS）. AS是指在一个实体管辖下的拥有相同选路策略的IP网络。 BGP网络中的每个AS都被分配一个唯一的AS号，用于区分不同的AS。）

BGP原理：
1.一般典型的外部网关协议路由包含了政策，安全性或者经济的考虑
2.鉴于BGP对传输流量的特殊兴趣，网络分为三类
　stub networks
　Multiconnected networks
　transit networks
3.成对的BGP路由器通过建立TCP连接来相互通信。
4.BGP从根本上说是一种距离矢量协议，但与RIP等大多数其他协议截然不同。（BGP router keeps track of the exact path.）

BGP报文有5种消息类型

1.Open消息：是TCP连接建立后发送的第一个消息，用于建立BGP对等体之间的连接关系。对等体在接收到Open消息并协商成功后，将发送Keepalive消息确认并保持连接的有效性。确认后，对等体间可以进行Update 、Notification、Keepalive和Route-Refresh消息的交换。
2.Update消息：用于在对等体之间交换路由信息。Update消息可以发布多条属性相同的可达路由信息，也可以撤销多条不可达路由信息。
3.Keepalive消息：BGP会周期性的向对等体发出Keepalive消息，用来保持连接的有效性。
4.Notification消息：当BGP检测到错误状态时，就向对等体发出Notification消息，之后BGP连接会立即中断。
5.Route-Refresh消息：通过OPEN消息告知BGP peer本地支持路由刷新能力（Route-Refresh capability）。

Main function of router

Design principles for Internet:

补充

Addressing

Def:目的是共享资源，与远端节点通信，要做到这一点，首先必须要找到目的节点，寻找目的节点的过程是寻址

两类addressing:
MAC addressing： 通过MAC address 定位目的地
IP addressing： 通过IP address 寻址

IP Addressing

步骤：
1.packet到达 一个router
2.The router forward the packet
3. Locate the destination

Process of router：
　open packet
　Decide destination network
　Look uo routing-table，re-encapsulation and forward

router主要功能
　routing
　Forward
　other

Routing table：
内容：网络地址，接口，metric，subnet mask，gateway等
　　　除了连接设备的IP和MAC地址，router还有她的邻居router的IP和MAC地址（APR table）
　　　因为不同的因素影响，可能有些不同

Internet protocal

功能：
协议：
1.
2.

IP packet format

结构：

版本号：4bits 识别用的是哪个版本：IPV6(0110)还是IPV4（0100）
IHL: 长度为4bits。IP head length（IP分组的头部是可变的），由于头的长度不固定，所以头的 IHL 宇段指明了头到底有多长（以 32 位字长度为单位），最小是5。
Type of service（TOS）：8 bits ，来区分不同的服务种类。可靠性和速度的各种组合都是可能的选择
Total length：16bits 单位是字节，包含了该数据报中的所有内容，即头和数据。最大长度是65 535 个字节

Identification：16bits，的用途是让目标主机确定一个新到达的分段属于哪一个数据报
DF和MF：dont fragment 和 more fragment：
Fragment offest：

Time to live（TTL）：8 bits 跳数，每次跳都会减一
Protocol：8bits 承载的数据是用什么协议处理的
Header checksum：校验和

source address：32 bit
destination address：32 bits
options：允许IP支持多种多样的不同优化比如安全性，错误报告，router等